Generally, a three-dimensional triangle mesh object comprises a plurality of triangles identified by their vertices. The triangle mesh is represented by a list of triangles, in which for each triangle the co-ordinates of its three vertices are indicated. The information in the list includes the co-ordinates of the vertices, and indication of which vertices belong to each triangle. The information regarding the co-ordinates is referred to as the geometry of the object, while information pertaining to which vertices belong to each triangle is referred to as the topology or connectivity of the object.
Elevation mesh data structures are triangle meshes defined by regular uniform X-Y grid spacing and a variable Z at each grid point. Elevation mesh structures are very common in LiDAR, Sonar, GIS, Geology, Geophysics, and other application areas, where data sets can be extremely large.
A triangle mesh representation of a complex, three-dimensional object can include a large volume of data. However, the communication lines through which such data may be transferred over the Internet or other networks typically have a limited average rate of data transfer, commonly referred to as bandwidth. Therefore, it is important to compress data objects as best possible before transfer. Similar issues arise with the storage of data representing complex surfaces. The better the compression method which is used, the more data can be transferred in a given amount of time or the greater amount of data which can be stored for a given resource.
One approach to reducing the volume of data required to represent an elevation mesh is to convert a regular grid structure containing uniformly similar cell sizes, into an irregular triangular network (TIN). In such a re-grid step, gradient, curvature or other measures are used to generate a triangle mesh which fits or corresponds to the original regular grid within certain error parameters. The advantages of a TIN over a direct elevation mesh are well-known. Often 90% or more triangles may be eliminated while still preserving a good fit to the original data. After modification, large flat areas are represented by large area triangles, while in small detail features small area triangles are used.
Many techniques for transforming uniform grid data to a TIN are known. One example is the open software implementation provided by Kitware described in a technical note, “vtkGreedyTerrainDecimation C++ Class Reference Documentation”, available for download from http://www.vtk.org/doc/release/5.0/html/a01452.html.
The vtkGreedyTerrainDecimation paper describes a top-down decimation approach that initially represents the height field with two triangles whose vertices are at the four corners of the original elevation mesh. In an iterative fashion, points associated with the greatest error as compared to the original height field are injected into the triangulation using a standard incremental Delaunay point insertion algorithm. Once the triangulation has been modified, the errors from the deleted triangles are deleted, and error values from the new triangles are added. In this way points are repeatedly inserted until the appropriate (user-specified) error criterion is met.
After modifying the uniform grid data into an irregular TIN, the modified data is can then be compressed using techniques such as those disclosed in “Highly Compressed Tessellation (PRC-HCT)” in ISO24517-1:2008 PDF/E SC2N570-PRC-WD.pdf (21 Jul. 2009 Edition) available for download from http://pdf.editme.com/PDFE.
The described approach distinguishes between stand-alone triangle processing and neighbor triangle processing.
For a stand-alone-triangle with vertices [V0,V1,V2], initially data for V0 is determined and stored. Data for V1 is then implicitly encoded by determining and storing a value for the vector V1−V0. Similarly data for V2 is implicitly encoded by determining and storing a value for the vector V2−(V0+V1)/2. When data for V0, V1−V0 and V2−(V0+V1)/2 has been stored a check is then made to determine if data corresponding to any of these vectors has already been stored when processing any other part of the triangle mesh. If this is the case, the explicit data for the newly stored vector is replaced with a pointer to the previously stored data.
A smaller data set for encoding triangles is achieved when processing connected triangles rather than stand-alone-triangles. This is because if two triangles share a common edge, once data for one of the triangles has been stored, data for the connected triangle only requires storing data identifying the other vertex of the connected triangle.
Thus for example assuming two neighboring triangles [V0,V1,V2] and [V0,V1,V3], connected by a common edge [V0,V1], once data encoding the vertices of the triangle [V0,V1,V2] has been determined and stored, data for the second triangle can be encoded solely by encoding data for the vertex V3.
In the PRC-HCT system data for vertex V3 is encoded as a point in a co-ordinate system relative to the centre of the common edge [V0,V1] in terms of unit vectors running along axes (V1−V0), V3−(V1+V0)/2)^(V1−V0) and (V3−(V1+V0)/2)^(V1−V0))^(V1−V0). Again once data encoding the new vertex has been determined and stored a check is made to see if corresponding data has previously been stored and if so the explicit data is replaced with a pointer to the earlier stored data.
In order to take advantage of the reduction in the size of the data set which arises through encoding triangles as neighboring triangles rather than stand alone triangles it is necessary to traverse the connected triangles in some defined fashion. In the case of the PRC-HCT method this is achieved by selecting an initial triangle and then parsing the triangle's neighbors. Neighbors of neighbors are then parsed followed by neighbors of neighbors or neighbor's etc building up a binary edge traversal tree. In this way the processing order is fully determined by the first triangle on the list and is not dependent upon any other triangle order.
Having reduced the size of a data set for a triangular mesh using the PRC-HCT approach, the processed data is then compressed using conventional data compression algorithms such as the Deflate algorithm in zLib written by Jean-Loup Gailly and Mark Adler. The Deflate algorithm is a lossless data compression algorithm which acts in two stages. Initially, data is processed to identify duplicate data streams and copies are replaced with references symbols. These symbols are then replaced with codes where the most frequent symbols are replaced using the shortest codes thereby reducing the size of the data. Further details of the zLib algorithm can be found in for example the DEFLATE Compressed Data Format Specification, L. Peter Deutsch, Aladdin Enterprises, 21 Mar. 1996, available for download from http://tools.ietf.org/html/rfc1951 which is hereby incorporated by reference.
Although data compression using terrain decimation and PRC-HCT compression reduces the size of data required to encode an elevation mesh, better compression schemes are sought in order to allow more rapid transfer and improved storage of data representing three dimensional data objects.